#ifndef lint
#ifdef __GNUC__
#define ATTRIBUTE(attrs) __attribute__(attrs)
#else
#define ATTRIBUTE(attrs)
#endif
static char Rcs_Id[] ATTRIBUTE((used)) =
    "$Id: mttest.c,v 1.16 2013-01-05 01:18:52-08 geoff Exp $";
#endif

/*
 * Test the Mersenne Twister PRNG
 *
 * $Log: mttest.c,v $
 * Revision 1.16  2013-01-05 01:18:52-08  geoff
 * Fix a lot of compiler warnings.
 *
 * Revision 1.15  2012-12-30 16:24:49-08  geoff
 * Use gcc attributes to suppress warnings on Rcs_Id.  Add tests for seed
 * functions.
 *
 * Revision 1.14  2010-06-24 01:53:58-07  geoff
 * Switch to using types and formats from inttypes.h.
 *
 * Revision 1.13  2010-06-24 00:29:38-07  geoff
 * Define the correct values as being explicitly 32 bits in size.
 *
 * Revision 1.12  2005-11-11 00:21:48-08  geoff
 * When timing, accumulate results in a temporary to make sure that the
 * compiler doesn't optimize all the code out of the test loops due to
 * inlining and discovering unused variables.
 *
 * Revision 1.11  2003/09/11 05:55:19  geoff
 * Get rid of some minor compiler warnings.
 *
 * Revision 1.10  2002/10/30 07:39:53  geoff
 * Update the correct-value table to reflect M&N's new seeding algorithm,
 * and the code to use it.
 *
 * Revision 1.9  2001/06/18 05:40:11  geoff
 * Do 300 million timing loops by default.
 *
 * Revision 1.8  2001/06/14 10:26:59  geoff
 * Test taking pointers to functions.
 *
 * Revision 1.7  2001/06/14 10:10:38  geoff
 * Report RNs generated per second.  Add some simple testing of state
 * saving and restoration.
 *
 * Revision 1.6  2001/04/23 09:19:03  geoff
 * Expand the validity test to 5000 numbers
 *
 * Revision 1.5  2001/04/23 08:36:42  geoff
 * Fix a misplaced declaration
 *
 * Revision 1.4  2001/04/09 08:44:59  geoff
 * Go from 1000 test values to 5000, and format them slightly more
 * neatly.  Get rid of a number of warnings.
 *
 * Revision 1.3  2001/04/07 23:09:38  geoff
 * Accept an argument giving the number of millions of PRN's to generate
 * in the timing loops (default 10 million).
 *
 * Revision 1.2  2001/04/07 22:21:41  geoff
 * Add timing tests.
 *
 * Revision 1.1  2001/04/07 09:44:16  geoff
 * Initial revision
 *
 */

#include "mtwist.h"
#include <inttypes.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/resource.h>
#include <sys/time.h>

int		main(int argc, char * argv[]);
static void	report_timing(unsigned long loops, struct rusage * then);
static void	report_clock_timing(struct timeval * then);

/*
 * Base unit for timing loops, so the caller can think in millions.
 */
#define TIMING_LOOP_BASE	1000000

/*
 * Default number of timing loops to do
 */
#define TIMING_LOOPS		(300 * TIMING_LOOP_BASE)

/*
 * The following table contains values that were generated by Matsumoto and
 * Nishimura's C program for the Mersenne Twist algorithm, using the
 * default seed of 4357.  These values are presumed to be correct.  The
 * test program compares the values generated by this implementation with
 * the reference values to ensure that the generator has been implemented
 * correctly.
 */
static uint32_t	correct_values[] =
    {
    3499211612u,  581869302u, 3890346734u, 3586334585u,  545404204u, 
    4161255391u, 3922919429u,  949333985u, 2715962298u, 1323567403u, 
     418932835u, 2350294565u, 1196140740u,  809094426u, 2348838239u, 
    4264392720u, 4112460519u, 4279768804u, 4144164697u, 4156218106u, 
     676943009u, 3117454609u, 4168664243u, 4213834039u, 4111000746u, 
     471852626u, 2084672536u, 3427838553u, 3437178460u, 1275731771u, 
     609397212u,   20544909u, 1811450929u,  483031418u, 3933054126u, 
    2747762695u, 3402504553u, 3772830893u, 4120988587u, 2163214728u, 
    2816384844u, 3427077306u,  153380495u, 1551745920u, 3646982597u, 
     910208076u, 4011470445u, 2926416934u, 2915145307u, 1712568902u, 
    3254469058u, 3181055693u, 3191729660u, 2039073006u, 1684602222u, 
    1812852786u, 2815256116u,  746745227u,  735241234u, 1296707006u, 
    3032444839u, 3424291161u,  136721026u, 1359573808u, 1189375152u, 
    3747053250u,  198304612u,  640439652u,  417177801u, 4269491673u, 
    3536724425u, 3530047642u, 2984266209u,  537655879u, 1361931891u, 
    3280281326u, 4081172609u, 2107063880u,  147944788u, 2850164008u, 
    1884392678u,  540721923u, 1638781099u,  902841100u, 3287869586u, 
     219972873u, 3415357582u,  156513983u,  802611720u, 1755486969u, 
    2103522059u, 1967048444u, 1913778154u, 2094092595u, 2775893247u, 
    3410096536u, 3046698742u, 3955127111u, 3241354600u, 3468319344u, 
    1185518681u, 3031277329u, 2919300778u,   12105075u, 2813624502u, 
    3052449900u,  698412071u, 2765791248u,  511091141u, 1958646067u, 
    2140457296u, 3323948758u, 4122068897u, 2464257528u, 1461945556u, 
    3765644424u, 2513705832u, 3471087299u,  961264978u,   76338300u, 
    3226667454u, 3527224675u, 1095625157u, 3525484323u, 2173068963u, 
    4037587209u, 3002511655u, 1772389185u, 3826400342u, 1817480335u, 
    4120125281u, 2495189930u, 2350272820u,  678852156u,  595387438u, 
    3271610651u,  641212874u,  988512770u, 1105989508u, 3477783405u, 
    3610853094u, 4245667946u, 1092133642u, 1427854500u, 3497326703u, 
    1287767370u, 1045931779u,   58150106u, 3991156885u,  933029415u, 
    1503168825u, 3897101788u,  844370145u, 3644141418u, 1078396938u, 
    4101769245u, 2645891717u, 3345340191u, 2032760103u, 4241106803u, 
    1510366103u,  290319951u, 3568381791u, 3408475658u, 2513690134u, 
    2553373352u, 2361044915u, 3147346559u, 3939316793u, 2986002498u, 
    1227669233u, 2919803768u, 3252150224u, 1685003584u, 3237241796u, 
    2411870849u, 1634002467u,  893645500u, 2438775379u, 2265043167u, 
     325791709u, 1736062366u,  231714000u, 1515103006u, 2279758133u, 
    2546159170u, 3346497776u, 1530490810u, 4011545318u, 4144499009u, 
     557942923u,  663307952u, 2443079012u, 1696117849u, 2016017442u, 
    1663423246u,   51119001u, 3122246755u, 1447930741u, 1668894615u, 
     696567687u, 3983551422u, 3411426125u, 1873110678u, 1336658413u, 
    3705174600u, 2270032533u, 2664425968u,  711455903u,  513451233u, 
    2585492744u, 2027039028u, 1129453058u, 1461232481u, 2809248324u, 
    2275654012u, 2960153730u, 3075629128u, 3213286615u, 4245057188u, 
    1935061435u, 3094495853u,  360010077u, 3919490483u,  983448591u, 
    2171099548u, 3922754098u, 2397746050u,  654458600u, 2161184684u, 
    3546856898u, 1986311591u, 2312163142u, 2347594600u, 4278366025u, 
    1922360368u,  335761339u, 3669839044u, 1901288696u, 2595154464u, 
     458070173u, 2141230976u, 4131320786u, 4208748424u,   19903848u, 
     147391738u, 3328215103u, 4196191786u, 3510290616u, 1559873971u, 
    3731015357u, 2918514861u,  362649214u, 1487061100u, 1717053387u, 
    3675955720u, 1116134897u,  193529268u, 3436267940u, 2835191639u, 
    1852908272u, 3220971953u, 3911201640u,  571213604u,  781027019u, 
    4219206494u, 1133024903u,  409547355u,  625085180u, 1214072539u, 
     584409985u, 3445042528u, 3733581611u,  333104904u, 2489812253u, 
    2694595213u, 2361631596u,   34763086u,  622576118u, 2921810672u, 
    3663740744u, 2293225236u, 2671706445u, 1884059696u, 1507329019u, 
     857065948u, 2204390003u,  592711182u, 1725752375u, 1642107460u, 
     326274448u, 3274574484u, 1030432041u,  173822100u,  529650788u, 
    1086437636u,  789877945u, 2167974914u, 1030588245u, 3533061365u, 
    1792148406u, 4216468704u,  213264131u, 3536714075u, 3877136173u, 
    1296338417u, 4057830103u,  205919137u, 2108245233u, 1064497347u, 
    2101324080u, 2336703164u, 1450493809u, 3812754708u, 3865701845u, 
    1476779561u, 1585902852u,  142887412u,  477612192u,  699530444u, 
    3351157089u, 3768249319u, 1673915577u,  903239649u, 1038056164u, 
    1171465372u, 1734789440u, 2115022236u,  414269055u,  959581346u, 
     566820984u, 2105828892u, 4046076449u, 4101450561u, 4106566571u, 
    2800184123u, 2470502098u, 3253453343u,  256751188u, 1869365987u, 
    1008372035u, 2374606708u, 1516804538u,  228288551u, 3527001547u, 
    1385173098u,   66157275u, 1739381798u,  184785808u, 3901692666u, 
     725806641u, 3475217997u, 2787929747u, 1109372433u, 3142723729u, 
     557686578u, 2782047723u, 2118822689u, 1936702581u, 1625646963u, 
    2349385293u, 3085804937u, 1272688179u, 1236112995u, 3198431244u, 
    2677635414u,  811555596u, 3486972196u, 2949678043u, 1342211552u, 
     788174404u, 1656614077u, 1582629285u, 1477167035u, 2687011245u, 
    3503701453u, 3351051324u, 2874557775u,  348432514u, 1629591495u, 
    3991682351u, 1969229192u, 3331660584u, 1304012077u, 2090754125u, 
    3910846836u, 1871998370u, 2098597104u, 1918921592u, 3246092887u, 
    1315760974u,  464122393u, 2184028058u, 1690455542u, 2193747147u, 
    3737423698u, 3511684278u, 1549884962u, 3413774919u, 3938991454u, 
    2767325310u, 2335626851u, 1626114941u,  601913200u, 3485711542u, 
     858447440u, 2288468476u, 4075602213u, 1506361431u, 4252489875u, 
    4032981007u, 1031118352u, 3762145731u,   70955369u, 2362903502u, 
    1669089455u, 2673510137u, 3348740333u, 2521337794u, 2047144929u, 
     892246357u, 2319875070u, 1293843163u,   79245769u, 2022600352u, 
    3866257397u,  989939126u,  835351312u, 3626278636u, 3805332945u, 
     836506264u, 1895040349u,  970326679u,  634920763u,  733185481u, 
    1028655248u,  977810701u, 3434484235u, 1871311609u, 2031584214u, 
    1336174158u,  385787519u, 3965885375u, 2768323462u, 1847726660u, 
    2718987737u,  793780050u, 2509902580u, 3886434164u, 3120956802u, 
    4207987247u, 1523159183u, 1884932179u, 2922324286u,  477253416u, 
    3037922812u, 1108379444u,  697195677u, 1755438379u,  574393398u, 
    2555059183u, 1930828628u, 1126190880u,  180621093u, 2589191337u, 
    3424652760u, 3054648512u,  719646637u,  952394946u, 3570038180u, 
     504304985u, 1395707758u, 1274213163u, 2816553213u, 1369142370u, 
    1804702100u, 1821782344u, 3358274235u, 2181234724u,  486158240u, 
     367287522u, 4267199121u, 1127352639u,  779850007u, 3440331597u, 
    3276765484u,  125500149u, 1142120513u, 3989398167u, 1048565860u, 
    3136747194u,  432668526u, 2098559576u, 1478877150u, 2484746208u, 
    1209580219u, 1019125185u, 4160278734u, 1970740713u,  918146921u, 
    4136433784u, 2602441845u, 2348512686u,  973030509u, 2238261365u, 
     815637919u,  994690313u, 1724736366u, 2099799816u, 1775069742u, 
    2680317667u,  730798472u, 2916864943u, 1284417767u, 1698724919u, 
    2733611686u, 1578128411u,  651006053u, 4243350375u, 3303874296u, 
     162087183u, 3796616231u, 3801767645u, 4119825424u, 3922537059u, 
      77594039u, 3419583692u, 2503306160u,  423966005u, 3293613218u, 
    1124728190u, 1407880681u, 1440346680u,  554334954u, 2919409323u, 
    1253962019u,  586491243u, 3638308238u, 3097648541u,  991125519u, 
     458538714u, 2155963569u, 2807866455u,    6862945u, 2122460897u, 
      53853750u, 3346001678u, 1230879976u, 3071060893u,  423909157u, 
    3881450262u, 1652511030u, 3826483009u, 1526211009u, 1435219366u, 
    3092251623u, 3001090498u,  281084412u,  849586749u, 2207008400u, 
     131172352u, 1820973075u, 3195774605u, 2962673849u, 2147580010u, 
    1090677336u, 2061249893u, 1724513375u, 3885752424u, 1135918139u, 
    2619357288u, 4012575714u, 2652856935u, 2029480458u, 3691276589u, 
    2623865075u, 3459550738u, 2097670126u, 2477000057u, 2209844713u, 
     785646024u, 1052349661u, 1030500157u, 1430246618u, 3807539761u, 
    2157629976u,  123154542u, 2560049331u, 2104110449u, 1332109867u, 
     721241591u, 4136042859u, 4203401395u,  998151922u, 3060999432u, 
    3207929139u, 2149509272u, 1385268511u, 2023309182u, 1366796638u, 
     256061060u, 4090836236u, 2929047008u, 2296609403u,  182240337u, 
    3744374619u,  306855912u, 4014087816u, 2240468995u, 2865233169u, 
     415452309u, 1244206523u, 3513921306u,  281425419u, 3511338031u, 
     995954022u, 3102854413u, 3026765331u,  643667197u,  837979907u, 
    2832983005u, 1813414171u, 2227348307u, 4020325887u, 4178893912u, 
     610818241u, 2787397224u, 2762441380u, 3437393657u, 2030369078u, 
    1949046312u, 1876612561u, 1857107382u, 1049344864u, 3544695775u, 
    2172907342u,  358500115u, 3895295219u,  571965125u,  328582064u, 
     744698407u, 3066193991u, 1679065087u, 2650874932u, 3570748805u, 
     812110431u, 3450423805u, 1705023874u,  259721746u, 1192558045u, 
    1714799045u, 3685508436u, 2262914445u, 3903852862u, 1790140070u, 
    2651193482u, 2821191752u,  776610414u, 2697125035u, 2212010032u, 
    1254062056u, 3541766210u, 1853927671u, 1543286708u,   66516686u, 
    3505195914u, 4226521519u, 1260092911u,  717982876u,  739240369u, 
     456195732u, 2116515161u, 1599487648u,  838913496u,  850912042u, 
    3712172413u, 2103192411u,  877020153u, 1458113119u, 2646869271u, 
    4087221703u, 3771198399u, 3952796001u, 1685641891u,  226245966u, 
    4065518354u, 3169076409u,  715963611u, 1155859114u, 4174181651u, 
    1816065125u, 2422210778u, 2353087594u, 2569974907u, 4049024520u, 
     563593555u, 1794197249u, 2434290377u, 4222178191u, 2381045132u, 
    1294739153u, 1333544226u, 3011196239u,  518183212u, 2861903570u, 
    3168787443u, 2315530531u, 1042490149u, 2998340365u, 3534153126u, 
    2862715604u,  796613230u,  765073073u, 1342937225u,  549817636u, 
    3786981820u, 4291017601u, 2895722553u,  734959362u, 3175258828u, 
     140019477u,  268621172u, 2410334776u,  565052604u, 3787587805u, 
     386344800u, 2874086067u,   35710270u,  817904650u, 1960697289u, 
    1584484509u, 2724312018u, 1978802819u, 2275314726u, 4216102886u, 
    2138332912u,  671754166u, 1442240992u, 3674442465u, 1085868016u, 
    2769242611u, 1003628378u, 1616076847u,  743729558u,  820011032u, 
    2559719034u, 1839332599u, 3121982280u, 2070268989u, 3769147733u, 
     518022934u, 3037227899u, 2531915367u, 1008310588u,  971468687u, 
    2052976098u, 1651926578u,   78218926u, 2503907441u, 3209763057u, 
    1081499040u, 2812016370u, 1247433164u,  335294964u, 2650385171u, 
    2030527826u, 1139372809u, 4279827824u, 3540669095u, 2285341455u, 
    4220507154u, 3863048231u, 3136394663u, 3319584205u, 1476940506u, 
     875141230u, 2508558662u, 3896001866u,  462864388u, 1609807693u, 
    3892563868u, 3642514037u, 3778083990u, 1403162576u, 3512254868u, 
    1403323269u, 1119818229u, 2831288053u, 2552740643u, 2520136409u, 
      96690857u,  210381252u, 1826474872u, 3306977352u, 1343117402u, 
    2112059492u,  693571694u, 2096734379u,  767794921u, 1843084587u, 
    1816280216u, 1695342628u,  404711915u, 3334843684u, 2570639553u, 
    4186538211u, 2022604264u, 3214805180u, 2989079529u, 2725165355u, 
    3005995436u,  310011850u, 2742468706u, 2720274646u,  144327376u, 
    2271696819u,  295519962u, 1272030376u, 1372670420u, 1397272558u, 
    2280044719u, 2710639434u, 2810822904u, 4271368265u, 1750711132u, 
    2216408539u, 3521792518u, 3111505866u, 3085328191u, 1054735512u, 
    4160317205u, 1427385632u, 2282061755u, 3215251668u, 1396490078u, 
    2933318719u,  453673969u, 2926038256u, 2624047458u,  338625410u, 
    3344930154u, 1971116345u, 1818716442u, 2998517928u,  390083048u, 
     291563131u, 1144486353u,  296954266u,  659950561u, 2263631666u, 
    1206908601u, 1125491020u, 1890151284u, 2076080514u, 2264060846u, 
     561805191u, 1964622705u,  405620012u, 3759692386u,  517035386u, 
    2225016848u, 4165419081u, 4052828294u, 3248204933u, 2738939733u, 
    1151808775u, 4113264137u, 3113447491u, 1033828852u, 1785686386u, 
    2903923175u, 2038900010u, 1241522880u,  238119113u, 2885394101u, 
    2636011022u, 2985605703u, 2107193353u,  292026696u, 3884689974u, 
    1094315383u, 4016714705u,  962244585u, 3943968050u, 2868319718u, 
    1304919603u, 3626636694u, 3393461291u, 1479454799u,  971639318u, 
    3352306399u, 1928233566u, 2900529135u, 2190901098u,   28842068u, 
     990556577u, 2586302532u, 3057504668u, 1661169605u, 4228191763u, 
    3934152427u, 2814119472u,    4943754u, 1171095774u, 1986204006u, 
    2014406505u, 1822565279u,   12890078u, 1979620724u, 1917376192u, 
    3307810835u, 4170173371u, 1385005883u, 1308519769u, 3370429606u, 
     923886311u, 2024463563u, 1063369787u,  153599761u, 3463680785u, 
     755374878u, 2088947962u, 3099927142u, 1750207400u, 2033606872u, 
     926120766u,  655932557u, 2320365045u, 1465119024u, 3105365454u, 
    2608716819u, 1218456091u,  823539591u, 2331574954u, 3171519129u, 
    3246671799u, 1043031086u, 1425831588u, 3940307546u, 3443545749u, 
    1155610704u, 3681098065u, 3287797558u,   63959365u,  810297004u, 
    3800799806u, 1234795257u, 2547289014u,  391329364u,  370300179u, 
    2474800443u, 3972311925u, 2935022755u, 3924395679u, 2347599539u, 
    4212318274u, 1828491430u, 3865565525u, 2767860661u, 4078993078u, 
    2781496513u, 4013741232u, 2916354756u,   35752471u, 2730683119u, 
    3340599926u, 4059491907u,  111492530u,  897368671u, 2524912702u, 
    3046341697u, 2790787159u, 1014602604u, 1409764839u,  512802978u, 
     477082227u, 2608350570u,  533747000u, 1933326657u, 4182933327u, 
    1970210993u, 2290203137u, 2843031053u, 2844558050u, 3308351089u, 
    3041943368u, 1504174920u,  295229952u, 2843309586u,  884572473u, 
    1787387521u, 1861566286u, 3616058184u,   48071792u, 3577350513u, 
     297480282u, 1101405687u, 1473439254u, 2634793792u, 1341017984u, 
    2500741117u, 4263797064u, 2322457777u, 1155622524u, 3736368257u, 
    3681071476u, 1137217259u, 1527337250u, 1366117744u, 3207345339u, 
     512022531u, 3628630048u, 4036536846u,  932603285u, 2772624172u, 
    4144438051u, 2059278872u, 3058844153u, 2745845437u, 4220526355u, 
    2339537870u, 3263741374u, 2780181639u,  830046989u, 2335972292u, 
    1514360419u, 3096871669u,  843103547u, 2244100243u, 3573704535u, 
    4267928843u, 4091363370u,  939208984u, 3295829276u,  454400120u, 
    3702127846u,  471147023u, 1957060850u,  273122868u, 1428866210u, 
    1737657854u, 3600299128u, 1925746977u, 2380738123u, 1571168523u, 
     519113682u, 3279227474u,  911322179u, 2696794428u, 2109856536u, 
    3315630517u, 1759453958u, 4006575573u, 3262077008u, 4177890150u, 
    1533579172u,  824755459u, 3314795869u,  596460132u, 4215683940u, 
    2990441121u, 3634236923u,  402953931u, 3584672586u, 2256594729u, 
    1577088289u, 2277811099u,  217436774u, 3698567316u, 4190005167u, 
    2082429185u, 3618893459u, 1689882188u, 3734303933u, 2883774800u, 
     324263298u, 3183678634u,  139054154u, 2233608349u, 2636817029u, 
    1493414555u, 3159722767u,  644233309u, 2643671789u, 2517246253u, 
    2845974520u, 1125905547u, 4085649601u,  190928872u, 1141978180u, 
    3242413680u, 3948731627u, 1042755180u,  508509300u, 1900103462u, 
    1344606968u, 2954061670u, 3745707120u, 1542873415u, 1003492034u, 
    3162556541u, 3470584807u, 1695255693u, 2390285737u, 2935248785u, 
    4052698114u, 3023860703u, 2163389899u, 1899687290u, 2862238469u, 
      84085276u,  656982819u, 1421023770u, 4179985759u, 1822395411u, 
    2722008140u, 1160802626u,  767294975u,  846339630u,  318440919u, 
    3529265600u, 2125900493u, 1846498371u, 3375757997u, 3812947227u, 
    1995784281u, 1680118162u, 3792592105u, 3303321146u, 2780428251u, 
    1704206566u, 3879390424u, 3472541629u,   25656479u, 3243031424u, 
    2978825284u, 1620901527u, 2512940888u,  927794181u,  452523305u, 
    3394773138u, 4253391568u, 4077229251u,  987808226u, 1406882831u, 
    1429828258u, 2883058504u, 2960876800u, 1883965824u, 4129270661u, 
    3579857811u,  973235694u, 3302203860u, 3969586611u,  718348498u, 
    3763448734u, 3702177983u, 1854328632u, 4251468518u, 2022446019u, 
    2209431908u, 2414211768u, 3797958050u, 3597530801u, 2525552689u, 
     636981785u,  664656278u, 2745678888u,  858404277u, 4276042326u, 
    1747857698u, 2746176763u, 3215666565u, 1887716830u, 3545855489u, 
     121927034u, 3392865382u,  357130402u, 1368051231u, 2277909715u, 
    2293787949u, 3358670926u,  386335223u, 3163867151u,  479772539u, 
     816735136u,  585372041u, 1124539534u, 2914789461u, 1942376489u, 
    2126769104u, 1975800425u,  814799998u, 2893249499u, 2126033825u, 
     760007658u,  633972488u,  806727295u,  236112176u,  414407704u, 
    3653783114u, 1391030845u, 2407584835u,  731546725u, 3992639691u, 
     106232033u, 2992162823u, 3567584453u, 2503068146u, 1051529903u, 
    3502104364u,  610035711u, 3775335972u,  667618167u, 4247343049u, 
    1301421152u,    2243584u,  144192006u, 3717030438u, 1757884509u, 
    2630952942u, 3363490445u, 4251803751u, 1904267860u, 2266368667u, 
      75111294u, 2059537251u, 1227434503u, 3441761728u, 4086217716u, 
     978577973u,  735792426u, 2139298718u,  404370445u, 3869131990u, 
    1176441999u, 2468151139u,  864851519u, 3630012660u, 3234610115u, 
    3172435896u, 3439750920u, 2516795165u, 2517212416u, 1059716705u, 
    2134575208u, 2862235859u, 2538210759u,  358555951u, 2442940989u, 
    2688476819u,  794989882u, 2838735245u, 3872585781u, 3134260357u, 
     105064119u, 3825751229u, 1135488310u, 4218960221u, 3360877465u, 
    3302954754u, 2575700988u, 2497293657u, 2388927109u, 3987074240u, 
     414604988u, 2491469147u, 3980520027u,   72941163u, 1711077678u, 
     519087922u,  171381824u, 3705314333u, 2513057424u, 2080037686u, 
    1774744635u, 3628627514u,  556341778u,  899387995u, 2615372983u, 
    2372073252u,  237968744u, 2705328516u, 3643402537u,  137400382u, 
    1941599746u, 2640174030u, 2083120893u, 1556545397u,  289682033u, 
     212740831u,  949213043u, 2102687076u, 2767525426u,  826825825u, 
    4191165775u,  528640652u, 4077394318u,  882590735u, 3163125263u, 
     629276741u, 1807552501u,  812058805u, 2945204393u,  183190693u, 
    2947275637u, 2728154303u,  993281047u, 1210608922u, 4272525031u, 
    2313255113u, 1870857999u, 2985702525u, 3194565035u, 2143686960u, 
    1451916006u, 2301248018u, 1558711357u, 1912047123u, 4251516193u, 
     532285070u, 3114187491u, 2106068513u, 3597063679u, 3663599168u, 
    1709549131u, 3753489627u, 3658005357u, 1160905342u,  737028908u, 
     895334719u, 4069027351u, 2426568775u, 1507089618u, 2750118357u, 
    1653041143u, 1791125727u, 1716827395u,  884658094u, 3085360311u, 
    4071341754u, 3590238451u,  352493133u, 4083973780u,  454018536u, 
     274798275u,  610061980u, 2854116038u,  714942167u,  757252280u, 
    2666997071u, 1593252771u, 2464064684u,  723272092u,  223672858u, 
     486201858u, 3999479492u,  655297946u, 3129578082u, 1698731657u, 
    3169005768u, 1702847708u,  272320271u,  120106603u, 3695564069u, 
    1932873871u, 4013239442u,  423242330u, 4227958558u, 3934266541u, 
    3689114116u, 2002816339u, 3373950165u, 3217483675u, 2204939216u, 
    3132445400u,  762796738u, 3162414255u, 1711928854u, 2819853427u, 
     575230348u,  926867967u,  132669602u,  221159232u, 4033582912u, 
     252108313u, 1294099693u, 1809928527u, 1269308130u, 3480686231u, 
    1429950454u, 1360727790u, 2006042568u, 3797144724u, 2783990950u, 
    1757106005u,  108354209u,  865723626u, 3617249860u,  109520212u, 
    2401026515u,  285359527u, 3668331347u, 2905102117u, 1494129763u, 
     348216553u, 1915669884u, 1414811767u,  232956812u, 1587333052u, 
     760671069u, 3422476798u, 2846738947u,  757998238u, 1420899728u, 
     398188339u, 3858968607u,  256042460u,  507472720u, 1232254610u, 
    4245222671u, 3075136024u, 2319205464u, 2119746088u, 3036187191u, 
    3887480239u, 4292783817u, 1737542162u, 1236303522u,  289379017u, 
    1780360736u, 1610718605u, 1996472339u, 3644617197u, 3281170667u, 
    1566409334u, 3514159615u,  612510353u,  430448254u, 1811185798u, 
     765006468u, 3732165767u, 1544620190u, 4282260204u,  243544799u, 
    2292191785u, 2241481909u, 1694649590u, 1442460355u, 1427073089u, 
     754492744u,  184820092u,  897419112u, 3678705335u, 3887604945u, 
     776070980u, 2900783033u, 1431582005u, 2012055595u, 1852695797u, 
    3917579167u, 1406433072u,  446726308u, 1084867033u, 3202096017u, 
     565067593u, 3162244645u,  388787811u, 2413176429u, 4089423644u, 
     791107632u, 1200634140u, 2565003219u, 2483173661u, 1288219555u, 
    1516166336u,  576053616u, 1361342997u,  913116636u, 3336073388u, 
    3843745245u, 1589908914u,  306887506u,  822428140u, 1041471861u, 
      47350214u,  230873349u, 1684806060u, 1897181775u, 3894132289u, 
      57050902u, 4240348943u, 3853407495u, 3044803004u,  844640504u, 
    2739986313u,  401023306u, 2667408852u, 1320130763u, 3973251787u, 
    1958752748u, 3782783511u,  436666731u,   83547082u, 4275166304u, 
    3094116720u, 1426327861u, 2538655628u, 1277094853u,  242713550u, 
     266482191u, 2743531761u, 1280948101u, 1273335605u,  199077170u, 
    1995269917u, 2170797334u, 4071342218u, 3270299293u, 2370531852u, 
    2710424997u, 2162130831u,  386081723u,  572675806u,  347301455u, 
    3062850063u, 3338222668u, 3973274791u, 3887524097u, 3880712621u, 
    2292533076u, 2732854883u,  468813770u, 1468745823u, 3546822021u, 
    2850369516u, 1452118653u, 2833005065u, 1262604654u, 1161523326u, 
    3205391754u, 2758572095u,   44395426u, 1843630982u,  208079731u, 
    3445477275u, 2868677914u, 1426717537u, 2591875243u, 3051602711u, 
    2259592887u, 2810102394u, 3134078220u, 1033606524u, 3037630581u, 
    3947578497u, 3355988886u, 2593461472u, 1236851705u, 1646026810u, 
    2974402225u, 3350613492u, 2390878749u, 2126029173u, 1703043827u, 
    3801306369u,  264529892u, 1709343735u, 3350828389u, 1193733634u, 
    1449911677u, 1041642862u, 2610764215u,    6405054u, 3183661914u, 
    1696457265u,  450169463u,  867572082u,  549276402u, 3316035838u, 
    2360256790u, 2613301818u, 2084044430u, 3346024089u, 3824563931u, 
    2144873191u, 3431508285u, 1651463044u, 3153970916u, 3567962109u, 
     220468773u,  549571972u,  313039992u, 1072303166u,  380222551u, 
    2161023965u, 3428890854u,  550663883u, 4050189100u, 4203427051u, 
    2936536013u, 3121879936u,  567291980u,  959491494u, 3104078241u, 
    2931645971u,  473964590u, 1927186295u,  504627954u, 2886471106u, 
    2751862512u, 3905695311u, 1412246296u, 3602455955u, 2808101279u, 
     910058066u, 3217495121u, 4084815289u, 2504763616u, 3770515788u, 
    3178414637u, 3045433914u, 1008573896u, 4169182346u, 3156618604u, 
    1816382062u, 4168688896u, 3596074775u, 3723437259u,  400803335u, 
     370374482u, 2892345381u, 1573833307u,  422498541u, 1585696786u, 
    2995703619u, 2942174909u,  927503844u, 2568139773u, 3340754484u, 
    3390292334u,  346761085u, 1579057249u, 1740755247u,  884882916u, 
     891164653u,  372229989u,  365212537u, 3315430932u, 2229872005u, 
     883365323u, 4202570990u, 1667613977u,  713352031u, 2369870728u, 
    3944817852u,  983346721u, 1308899441u, 2757113982u, 2494900868u, 
    2080827335u, 3624427103u,  652171563u, 1666757625u, 3358372252u, 
      25827967u,  432100882u,   42605297u, 1263005308u,  852004783u, 
    1019509360u, 1689563162u, 2280078981u,  844049518u,  392984060u, 
    3587407155u, 1740816471u, 3348953483u,  450311223u,  331586083u, 
     482255964u, 1251638867u, 3369092147u, 1183178495u, 1252284967u, 
    2670206902u, 2592156382u, 3956400143u, 4142163820u,  968164509u, 
    1857508915u, 1223187601u, 2983937972u,  363499219u, 3256011603u, 
    1407877715u, 1858184655u,  223762808u, 2815342624u, 2623728343u, 
     471394359u, 2338922152u, 4010468018u, 1494235404u,  805138023u, 
    2263304220u, 1143229406u, 4294371569u, 3426654861u, 3673268051u, 
    2094242240u, 3878198506u, 3302650596u,  553215323u, 1700836024u, 
    2644918481u, 1172263171u, 3566289616u,  159921530u, 4242701100u, 
    2891779620u, 2772910690u, 1844965307u, 3222652689u, 1940205226u, 
    3252887615u, 2619316586u, 2863214944u,  255135220u, 2319400461u, 
    1356399792u, 3136420082u, 3318816270u, 3348965492u, 2991156919u, 
    2098723029u,  538297620u, 2550174061u,  558996197u, 4153977074u, 
     396650285u,  336629528u,   33587922u,  151050341u, 1817240964u, 
    1598635540u, 2815665370u,  334635542u, 3104928583u, 3368059279u, 
    2281526556u, 2049214434u,  467369481u, 1892587657u, 2713415926u, 
    1210292261u,  543312793u, 2219660615u,  576828305u, 1579949228u, 
     423458407u,  506340086u,  610002369u, 2571074778u,  722633826u, 
      71222137u,  842882706u, 2009087692u, 1363565258u,  457448717u, 
    1359052209u, 1454830478u,  934427297u,  373198223u, 1078216524u, 
     881146725u, 3835072521u, 2223843980u, 3020320737u, 2047751094u, 
    2386876295u,  151140833u,  792136558u, 3664204416u,  910665524u, 
    4082855445u,  332202002u, 3663329916u, 3924742864u, 4210357809u, 
    3035318721u, 3703582172u, 2395685358u, 3527486801u, 1346167233u, 
    3945460735u,  713838878u, 2569385804u, 2673605345u, 3550969220u, 
    4243147364u, 2309000764u,  731999942u, 3921900019u, 1107209281u, 
     720619514u, 1704240103u,   81125990u,  317805114u, 3678640075u, 
    2938170218u, 3613685474u, 1728244724u, 3385237271u, 4221245045u, 
    3133258246u, 1727367040u, 3154857385u, 2665765720u, 2518841063u, 
     663013272u, 2419053996u, 1637865178u, 3969548484u,  692065125u, 
    2599473883u, 3256068101u,  435175331u, 3741393791u, 2658647268u, 
    1506574630u, 3151733449u, 2944353448u, 1249681632u, 1263358766u, 
    1368483368u, 2279035519u, 2464850890u, 3575231217u, 2754206804u, 
    2566200848u,  238034272u, 1440151198u, 4208701947u, 1285161672u, 
    3403832724u, 1943870151u, 2745258239u, 1815249255u, 1392971118u, 
    1544497359u, 4177624680u, 2397962695u, 2169967634u, 3189208041u, 
    3957569271u, 1822504027u, 2446464090u, 1844069058u, 1917044074u, 
     536324405u, 4142347706u,  104943297u,  516241068u, 1246336192u, 
    4230215670u, 1363740512u,  987712840u, 2807577755u, 2564077993u, 
    4110008491u, 2449624894u, 4018933476u, 3284119631u, 1966606846u, 
    1770310834u, 1032846869u,  240023392u, 3280916673u, 2173260788u, 
    3261286273u,  738911634u, 3181059220u, 2272149255u, 3194117094u, 
    2295733216u,  454924713u, 2932109539u, 2927279746u, 2029061725u, 
    1989689036u, 1420837132u,  911234017u, 1608529501u,  423134779u, 
     592387170u, 3537225433u, 3132705035u,  751661097u, 1414330162u, 
     702527398u, 2836854972u, 2860393334u,  273776580u, 3841373097u, 
    3897191802u, 2218600621u,  449503320u, 3018083450u,  426281553u, 
     659665656u, 1685861555u, 4095066912u, 2859028254u, 2323079437u, 
    2128578931u, 2919434878u, 1985959120u,  157036961u,  907467960u, 
    3475504086u, 1758801206u, 3215293590u,  462673225u,  516199313u, 
    2101618132u, 2255051833u,  480276182u, 1399444775u, 1540169926u, 
    2346982492u, 1248385475u, 1713179789u, 1407905589u, 1782812514u, 
    1112519953u,  776262767u, 2341647152u, 1096877715u,  299066250u, 
      88200511u,   74481227u, 3967156568u,  579473510u, 2807619625u, 
    3850609488u, 4005544769u, 3188251219u,  702280284u, 2592713719u, 
    3956082585u, 4092611494u, 3413029630u, 3926299537u, 2479889188u, 
    1040891653u, 1889938488u, 3874351210u, 1106442576u, 1903244241u, 
    3229585166u, 2416701998u,  982127964u, 1508122208u,  275681456u, 
     157531183u, 3295655144u, 2421430989u, 2882791436u, 1491165734u, 
    3071814346u, 3314520194u, 2757630249u, 2706643074u, 1799798708u, 
    3833725166u, 1678310352u, 3702234087u, 3505295054u, 1450032842u, 
    1363342287u, 2850921603u, 3498421664u, 2939309820u, 3389044949u, 
    1718335002u, 3660445557u,   78993494u, 2171692745u,   17549235u, 
    2730144888u, 1676319386u, 4084060395u, 4294716373u, 1906811545u, 
     859270623u,  257778878u, 2697422981u, 3722662433u, 3949147603u, 
    2710934973u, 3662672644u, 1525029711u, 3555554520u, 4282096432u, 
    3966879769u,  962809256u, 1184851100u, 2802256012u, 2770295670u, 
    2598415034u, 1796104491u, 1663206446u, 4260805312u,  610689191u, 
    2021836756u,  107953943u, 2900545767u, 1808663339u, 4008622457u, 
     790704710u, 2452868627u, 3117181052u, 1882665914u, 1590695627u, 
    1374587697u, 3614473030u, 3931887505u, 3153492485u, 4218122191u, 
    2452537456u, 1201324194u,  759586707u,   84942475u, 4111933087u, 
    1444391735u, 1139549443u, 3805974531u, 3971044720u,  477880684u, 
     961086587u, 1340362124u, 1604444345u, 2254105549u,  375811159u, 
     512712169u, 2749279630u, 3267939599u,  775743625u, 1342835433u, 
     193493042u, 1241189548u, 3106006437u, 1399344769u, 1492233317u, 
    1768053880u, 2837327654u, 1131098881u, 1648703102u, 2089150983u, 
    2694432705u,  973706044u,   92985242u, 3999906913u, 3910868338u, 
     191327779u, 3438373242u, 4193928044u, 3203390558u, 3362940567u, 
    3492292949u, 1934984940u, 1646288108u,  918962490u, 2651194120u, 
     442802528u, 2471731585u, 2340716146u, 2276554727u, 2302476915u, 
    1181415588u, 2868758587u, 1067853265u,  347176489u, 1939773730u, 
    2777887450u,  978019153u,  625959233u, 3455084654u, 1731268224u, 
    4235285461u, 3944667737u,  128814437u, 1818688919u, 2300660171u, 
    2758723882u,  373993792u, 2644214523u, 3444956489u, 3434458008u, 
    4248345024u, 1901574406u,  287531999u, 3007537762u, 4034685229u, 
    3517853408u,   78071904u, 1139716314u, 2937064484u,  239252817u, 
    3366122534u, 3038632949u, 2294103376u, 3438832446u, 3802589858u, 
    4154544779u, 3861196633u, 4260830112u, 2688381633u,  181409553u, 
     592142795u, 3965383578u,  935450750u,  269811790u,  782289952u, 
    1638485324u,  179614966u,  548548887u,  459310932u, 1886180225u, 
    2647604623u,   36947705u, 4035813282u, 3753815615u, 1522375757u, 
    3809696647u, 1763638499u, 2226920609u, 4227748553u, 1313305235u, 
    4061231705u, 1702505565u, 2906166764u, 1729326608u, 4244725906u, 
     966149927u, 3293515724u, 2367813487u, 1446112345u, 1227910659u, 
    2844908425u, 1594427357u, 1048681939u,  212427838u, 1269193978u, 
    3496717749u, 2921343850u, 2668456969u, 2267084882u, 1334928840u, 
    1767780686u,  983963396u, 2588311435u, 1850331400u, 3223459079u, 
    3111775696u, 2506255888u, 3702554614u, 2369930792u, 2929647161u, 
    2506416716u, 2479117917u, 2198249807u, 3444428083u,  354733066u, 
     717644749u, 3090530204u, 2738017268u, 4278457915u, 4258807760u, 
    1522713227u, 3905745313u, 4171524857u, 2035336180u, 1487986097u, 
    2620568311u, 3807676884u, 3856083492u, 1952899566u, 3060080941u, 
    1775656683u, 1827822866u,  935152116u, 2266271948u,  539682350u, 
     981783224u, 1326778049u, 3842197721u, 3118594795u,  467228000u, 
    3362409922u, 4079824256u, 2979795106u, 1709741046u,   42100360u, 
     120392511u, 3621573700u, 1920136592u, 3961385783u,  884407395u, 
    3311223137u, 3826235090u,  183222673u, 4039028327u, 1624297109u, 
     326318752u, 3025115648u,  594985212u, 3133234670u, 2207588835u, 
     963262671u, 3724108540u, 1155581262u, 3462905334u, 2890646829u, 
    3607969926u, 2050813368u, 3936879051u, 2678841578u, 3541348965u, 
    1015523243u, 2818254642u,  760740720u, 3880905941u, 3563291220u, 
    1196395351u, 3293903482u, 3540091169u, 4013553601u, 2934740932u, 
     463379296u, 3078765390u,  782661164u, 3353858244u,  425610981u, 
    2844388125u, 2103519494u, 3224691896u,  829982391u,  868188911u, 
    3847825001u, 2442903745u,  425586795u, 2785754810u,  189689674u, 
    2997051076u, 2393564453u, 2738132518u, 3317841037u, 3475188031u, 
    1339772322u, 3390183362u,  768723894u, 3115470760u, 1455803558u, 
     116426970u,  902568622u, 4093525619u, 2191088390u,  585691733u, 
    3892805143u,  897281696u, 2701207772u,  561461717u,  436084723u, 
    3742605163u, 1678708375u, 3817938705u,  234576607u,   27356943u, 
    2152993718u, 2986534572u, 1854228316u, 3521019125u, 4284489069u, 
    2810677824u, 3485806537u, 1976235678u, 2085858020u, 3148717547u, 
    3841623852u, 2435052650u,  590758137u, 1905986752u, 1675058364u, 
    2257780991u, 3982964645u, 2430544059u, 3940605995u, 2752661619u, 
    3064777055u, 2559949677u, 2655738818u, 3295104124u, 1474410264u, 
    2912446382u, 4020206781u,  576447599u,  535900431u, 1077310659u, 
    3137840249u, 1423157467u, 2776599449u,  787981617u, 3578360533u, 
    2556456226u, 1710609124u, 3325599781u, 3220461886u, 1478864177u, 
    3587244773u, 1268625412u, 1384956853u, 3882391248u, 2371945596u, 
    2045842833u, 4205327602u, 2464830712u, 2359262182u, 1171364609u, 
    1419158616u,  682715999u, 2660610073u, 2991823783u, 1548922277u, 
     831618797u, 3249183760u,  597636688u, 1777690202u,  458256856u, 
    2114606129u, 1299095260u, 2983899478u, 1264581214u, 4177860236u, 
      17273196u, 1407696854u,  593370470u, 3598337265u, 3195346021u, 
    3174291042u,  741107679u, 4098148086u, 2795583024u,  137106654u, 
    3452336576u, 1532740620u, 2229449622u, 2846076572u,  380183779u, 
    1209039979u, 2995172882u,  989487735u, 3715237075u, 3054273866u, 
    1955734715u, 2682520233u, 3818975284u, 2536644837u, 2284983225u, 
    2836559461u, 1389069601u,  204245791u,  777929392u, 1498019328u, 
    2401467298u, 1938493040u, 1071806041u, 1034679075u, 1620524703u, 
    3071094964u,  439558162u, 3677274935u, 4238774239u, 1209066361u, 
    1088039431u, 3139839398u, 1795448587u,  591687111u, 1875516399u, 
    3593696961u, 3145148511u,  595289847u, 1648586281u, 2526340071u, 
    1268107314u, 1572631480u, 3645616041u, 3465005871u,  544293197u, 
    2163721987u, 2048400380u, 2102791667u, 3372026220u, 3766895552u, 
    4286553780u, 1516732531u, 3412212465u, 1930345401u,  117250582u, 
    4138331062u, 4120218221u,  181667649u, 1440931813u, 4178824234u, 
     201952914u,  812637199u, 2602482807u, 2865259846u, 4183543706u, 
    2518738954u, 2969539593u, 2899585754u, 2896888904u, 1550577888u, 
     862479326u, 2664075557u,  897196313u, 3483866497u, 3708057157u, 
      82710238u, 3717454735u,  360233959u, 3097186829u, 4186741298u, 
      86621536u, 2797524946u, 1609114124u,  993158854u, 1345445936u, 
    1732981263u, 2140204917u,  524074125u, 3131818693u, 1152935964u, 
    3070648776u, 1107440887u,  541231638u, 1424491339u, 3438607874u, 
     653840126u, 1420721291u, 1494681525u, 1776801700u,  522519102u, 
    1413795107u, 3797408458u, 2643175199u,  404922594u, 1348222327u, 
    3994494069u, 3366587261u, 1713777698u, 2879553944u,  203587743u, 
    2308248086u, 1470483001u, 3099400086u, 3160950562u, 3134392672u, 
    3413133866u, 2746553770u, 2340353022u, 2732453903u, 2947307338u, 
     438129945u, 3838123218u,  492730903u,  235328936u, 2388344531u, 
    1304215689u, 2005591534u,  198391212u, 3193756469u,  839566305u, 
     393940610u, 3093088558u, 3423367095u, 3099906696u, 2343498361u, 
    3770118303u, 4168129773u, 2501530535u,  883925372u,  303586901u, 
    3868847116u, 3963157752u, 3157301259u, 3437571950u, 3392902953u, 
    1228132404u, 1707178093u, 2335015782u, 3904565878u, 4229581755u, 
     492138180u, 3073813901u,  640665822u, 3603346999u,  922161726u, 
    1860839953u,  560459819u, 2021317766u,  297881981u, 2408245790u, 
     384530297u, 1155739363u, 2562994192u, 3217009820u, 4110041205u, 
    2164181515u,  519027455u, 2778026350u, 3674648725u, 1321757186u, 
    3531453112u,  595817782u, 2027376578u, 2042570202u, 2888809226u, 
    1556750754u,  704400727u, 3384921396u, 3289703113u, 3351345046u, 
    1037627351u, 2871238084u, 2307943700u,  573394694u, 3105141941u, 
      92581831u,  882519770u, 2404497529u, 2508795700u, 1292007850u, 
     620527306u, 4034734001u, 1963769227u, 4212949030u, 1791638453u, 
    1231025186u, 1700222598u, 3439496951u, 1936785558u, 3848768958u, 
    2681320752u, 2566357103u, 2405639388u, 3796822945u, 3362218643u, 
    4053296118u, 1293805338u, 2358616019u, 3463138327u, 3128397576u, 
    3015879164u, 2477158023u, 1475962738u,  111057009u,   88496518u, 
    1917835954u, 1662174364u, 2775845786u, 1363900744u, 2238549646u, 
     578031776u, 1599070698u, 1870290001u, 4024962733u, 3205774627u, 
    3562816366u,   40250330u, 3646794336u, 4283270024u, 1600022383u, 
    1209132687u, 2547708346u, 4168140719u, 3747584726u, 3382580702u, 
    4009358868u, 4201204527u, 2871032209u,  661220876u,  888098135u, 
    1666178348u, 2808266895u, 3943189777u,  309459048u, 2163423368u, 
    1746878799u, 1974582532u, 2864449124u,  509670988u, 4010321183u, 
    2575074271u, 3483003844u, 3644480339u, 2081118997u,  652915824u, 
    3250213093u, 2752162620u, 1791205177u, 3047448045u, 4173789058u, 
     348953149u, 4243319035u, 3095301674u, 3711485381u,   14525930u, 
    1670243072u, 3689494100u, 1953101249u, 4234735905u, 1059513456u, 
     831806169u, 3369071539u, 1444988928u, 3791758648u, 2638473230u, 
    3924361789u, 3909317902u, 2397815488u,  108384758u, 2572118926u, 
     525129562u,  639420665u,  669144050u, 3864239974u, 3201253704u, 
    1934425697u,  433412542u,  883355992u,  495200818u, 3863971557u, 
    4033311018u, 3275279952u, 2148897016u, 3790249833u,  731766156u, 
    1223851860u, 3678193481u, 2891483608u, 1426705768u, 2853060454u, 
    2263653682u,  527486390u, 1913529154u, 1749419299u, 1353895017u, 
    1182348463u,  659872483u, 3078073095u, 1352634951u, 1217126631u, 
    3663266877u, 3849144771u, 1728881200u, 3550129307u, 4033329575u, 
    1675151111u, 1759466246u, 2138476840u, 3303545893u, 2984165585u, 
    1559521459u, 3583587581u, 2754204271u, 2618339581u, 3734997486u, 
    2468477297u, 3982798873u, 1400340476u, 1775731536u, 1960328724u, 
    3992723360u, 3065728698u, 1881136493u, 3798490745u, 3473259209u, 
    3096051547u, 1515970810u,   79941263u, 1441182150u, 2898142851u, 
    1399408592u, 1883381057u,  416509126u, 1880423351u, 3093448915u, 
     502669317u,   27468357u, 3499031203u, 1762592447u, 1395243464u, 
    3871613901u, 1057541701u,  267568056u, 1471942076u, 3842828346u, 
    1613585440u, 1973730051u, 2347430656u, 1449022602u, 2413428676u, 
    1816723564u, 1700043520u,  935486730u, 1709959123u,  418061874u, 
    2213485346u, 1066247998u, 2824072173u, 1935834272u, 4084149685u, 
    1854534142u, 3102463245u, 1791912859u, 1718329419u, 1895590262u, 
    3572860213u,  657834953u,  576978784u,   43442786u,  259702811u, 
    3218038282u,  361838311u, 4090401236u,  703937918u, 3905131145u, 
    1392513962u,  318722468u, 1295906647u, 2204048009u,   50169489u, 
     387845619u, 2318874730u,  137969335u,  409622605u,  505726246u, 
     629276521u,  643912174u, 2710730823u, 3662425714u, 3690753083u, 
    1056548235u, 4184250032u, 3922653458u, 2451732360u, 3394781897u, 
    4281439047u, 4108402885u, 2377442948u, 1495144293u, 2213877196u, 
    2950896548u, 1420268666u, 2523549781u, 1846843665u, 1787890598u, 
    2112291765u, 4187105389u,  305101977u,   28097139u, 3812810910u, 
    2427959932u,  277599151u, 3192572462u, 1873400110u, 3204284336u, 
    3550346696u, 1186049286u, 1694513554u, 4015601921u, 2634854552u, 
    3468396689u, 3516035178u, 2194659629u, 3806350498u, 1790891005u, 
    3999094007u,  668799895u,  819413823u, 4265177898u, 1110602326u, 
    1230733198u, 3856303761u, 1152893805u, 2548469791u, 3362430037u, 
    2163976689u,  261211212u, 2631997142u, 3049954710u, 3519391742u, 
    2684474998u, 2284446581u, 3767319453u,  867905936u, 1477946054u, 
    1949457599u, 3082436333u, 1837863418u, 1909772278u, 4149164990u, 
     777712915u, 2663116186u, 2580037763u, 2986677112u, 1805877811u, 
    3093083469u,   47479577u, 1489903495u, 1265001771u, 2220456937u, 
    2751664031u, 2390985243u, 2999864559u,  672141846u, 3231315389u, 
    2414012330u, 1906819045u, 2984157392u, 3741192015u, 1831612599u, 
     412535655u, 3591754091u, 3679838215u, 3141283535u, 1326459140u, 
    1546321559u, 2053959246u, 1950827292u, 2489596315u, 1659531982u, 
    1336558483u, 3330981825u,   97580289u, 3153670395u, 2324499306u, 
    1848029250u, 3326835115u, 2979644611u, 1264461714u, 4059661017u, 
    3104006826u, 3368253358u, 2397455377u, 3030408045u, 3174369033u, 
     469586980u,  951616564u, 1674739403u, 3784254295u, 2537916485u, 
    1629754480u, 1973022275u, 1402612676u,  216208581u, 2781646564u, 
     982205675u, 4075937534u, 3582814745u, 2136790623u,   67193454u, 
     468091581u, 3709609904u, 4109050590u,  335304015u, 3973380988u, 
    2873516039u, 1614829131u, 2148391288u, 1996647808u,  936276241u, 
    1659295594u, 2455070843u, 4092282313u,  524798420u,  958595957u, 
    2882637010u, 3874299566u, 2575200323u,   45864893u,  240415769u, 
    2863710934u,  241991393u, 4026751870u,  654985261u,   73118816u, 
      84271844u,    9504786u, 1869064740u,  105677904u, 3574364025u, 
    2599606066u, 2651670594u,  438506082u, 2233938841u, 1670640089u, 
    3710285779u,  745377473u,  419609375u, 2602573397u, 3900054502u, 
    2650521038u,  463928187u, 1172984423u, 2220484190u, 1095807452u, 
     614850457u,  144205315u, 2402478324u, 1451658947u,   19669332u, 
    3097977779u, 3292874081u, 4095144717u, 3645178392u,  463290186u, 
    3937717357u, 3760375802u, 4238996472u, 1930769438u, 2169530151u, 
    1121118212u, 1165746984u, 3261547512u,  432720133u, 3457041397u, 
    2181194120u, 1036791209u, 2515172049u, 1493671637u, 3276575128u, 
    3151035990u,  356321858u, 1170285938u, 2841534012u, 3818274169u, 
    2220407942u, 3339536836u,  734645661u, 1250564386u, 4031075337u, 
     632013612u, 2536105946u, 1968372804u, 1892511539u, 3134146239u, 
    4045511005u, 3378295560u, 2817128396u, 3086852652u, 1941092040u, 
    1186603069u, 3606472960u,   70669832u, 2287600530u, 1638569324u, 
    2378926845u, 2315380185u, 2920859214u, 1455582985u, 1577068627u, 
    3591589856u, 1027745331u, 2126182285u, 2486457443u, 3623598128u, 
    3723251533u, 3911666366u, 1747092880u, 2402125269u,  483678340u, 
    1575314013u, 1906303350u, 3383365516u, 1289282189u, 1339901439u, 
    1723943420u, 2439753462u, 3579269267u,  363627112u, 1733571930u, 
     314184313u, 1675792864u, 4020770502u, 1548116196u, 2273911152u, 
     602392177u, 2838838375u, 1117250656u, 2740063266u,  372868020u, 
    2552512122u, 1844247494u, 4264502803u, 1105021132u, 3544737911u, 
    1277990640u, 2641105602u, 1824752961u, 3181211334u,  511991294u, 
    2236096341u, 2126296232u, 3094295258u, 3033995959u,  527724412u, 
    1046139663u, 2931463347u, 3371850311u, 3083598147u,  318212288u, 
    2898050586u, 1691716442u, 2861896595u,   14577642u, 2030754905u, 
     947800038u,  246325017u,    5585911u, 1615345507u,  812520481u, 
    2683069823u,  611964371u,  490907220u, 1151377635u, 2292093180u, 
     751155690u, 2811469882u,  595492796u, 4108972367u, 2572194110u, 
    4103704225u, 3870014217u, 3853331788u, 4034605360u, 3891903368u, 
     949980031u,  623024259u, 2073057785u, 1616375580u, 1614955440u, 
    2929877158u, 2249618123u, 2290570578u, 1137619107u, 3073303314u, 
     293592020u, 3539009164u, 1874010544u,   18293765u,  746693114u, 
    2924999677u,  112129180u, 3183436706u, 4100311944u, 3942948478u, 
    1849397958u, 2492102702u, 4129862629u,   89745884u, 3274545262u, 
    3595635232u,   31562271u, 2564379334u, 2920743717u, 1180122591u, 
    3032035420u, 1353651248u, 2770807059u,   25081401u, 2372152730u, 
    2069576326u,  936769856u,  723606552u, 3317287620u, 1611064790u, 
     979374201u, 2204611921u, 1592851823u, 4191754721u, 3826510149u, 
     720641424u, 3678110796u, 3723533932u, 1728438917u, 3122163332u, 
    1365881714u, 1765132094u, 2614069276u, 2921135690u, 3909258731u, 
    1560697876u, 3904546998u, 1269385037u, 2540878633u, 1980234534u, 
    1428383314u, 2964988624u, 3663880395u,  652791181u, 1900084498u, 
     326298089u, 3884177206u, 2537320201u,  142504470u, 2075689920u, 
    2286754314u, 3471190679u, 3077332658u, 4148280726u,  770095561u, 
     446553822u, 1445397914u, 2998794260u,  806220989u, 2035613576u, 
    1382666746u,  464938132u, 1734551383u,  940041372u, 2356074312u, 
    1821789369u,  209330661u,  812406143u, 2373966445u,  463302805u, 
    1180306011u, 1656902011u, 1037242088u,  359039185u, 1044300592u, 
    2379839739u,  662109823u,   74469949u, 4107776963u, 4280041364u, 
    4018634993u, 4291500862u, 3516351734u, 2761187869u, 3127860814u, 
    2593569870u,  755105602u, 3113400158u, 1547781563u, 3331942386u, 
     810846783u,  846702952u,    5147099u,  434277085u, 1359011478u, 
     979453305u, 3004832082u, 1651070055u, 2685450541u, 3023061945u, 
    2332434296u, 1449076389u, 1885650424u, 4063755770u, 1234490702u, 
    3464987032u, 2154609442u, 2310908165u, 3270815960u, 3468813887u, 
    3274517632u,  503947210u, 2474141277u, 1287887592u, 3211187438u, 
    1624803533u, 2772549594u, 3171469972u,  529223794u, 3413509397u, 
    2166372317u, 3391791557u, 1491475969u, 1785826673u,  395771269u, 
    3844001065u,  635008637u, 2943484153u,  851132384u,  152778962u, 
    2887378673u, 3751896912u, 1853326403u, 2472544967u, 2982442106u, 
     310002530u, 1102881285u, 2867283667u,   41913069u, 3504408015u, 
    2286138391u, 1935548655u, 1199979353u, 3426129152u, 4064027578u, 
    1591439016u, 3893144160u, 3401059997u, 1686567419u, 2610861827u, 
     106752445u,   66861635u, 2883799100u, 1424012493u, 3595620492u, 
    2699922466u, 4172559189u,  888884433u,  244524878u, 2283218712u, 
    1934126058u,   40293409u, 2501690904u, 2261381514u, 2949086966u, 
    1806374300u, 3089940133u, 2157022662u, 2791903748u, 3568420276u, 
    3122074238u, 2034253194u, 1605663501u, 1405079440u, 2497876014u, 
    3669352834u,  498725211u, 4140305918u,  247623610u, 1595801470u, 
    4208059585u, 1440824281u, 1223308576u, 2146301246u, 2555395148u, 
    2596810779u, 4132450170u, 2372835596u,  797911580u, 1831738774u, 
     829099694u, 2207504167u, 1467350244u, 2190713264u, 4006765973u, 
     140374436u, 1677904306u,  722287139u, 1173456818u, 3433373317u, 
     652607730u, 3578901879u, 1705569489u, 2756232453u, 1609420758u, 
     621700234u,  563133390u,  372364134u, 1868485656u, 3193050428u, 
     393046075u, 1655111696u, 2639802682u, 3745421913u,   47154834u, 
    3533792021u, 2462134617u,  833305539u, 3391863910u, 1193916378u, 
    1010892576u, 2314992090u, 1924230043u,  173327386u, 2445374764u, 
    3344539005u,  263717207u,  344458992u, 2131544513u, 2844286976u, 
    2758722915u, 1914807185u,  950329081u, 2499332236u, 3595130050u, 
    1404646615u, 4170736375u, 1208124202u, 3635143895u,  115864937u, 
    2173251121u, 1455416724u, 1197761604u, 3962211850u, 3206696551u, 
     856644982u, 1017608232u, 3649849172u, 4111766657u, 2621815082u, 
    2663996565u, 3485608353u, 2578106283u, 1608204161u,  741330692u, 
     230735732u,  388036276u, 3976257312u, 1096342811u, 3792877416u, 
    3687532372u,  143297888u, 3913003182u, 4134793368u, 3004904148u, 
    2873860186u, 3114634496u,  330405231u,  987353207u,  872230598u, 
    2474130781u,  489623837u, 3481621200u, 2178025230u, 1734494073u, 
    1599344169u, 4245314329u, 3047428366u,  386541963u, 2019633251u, 
    1378431249u,  961885261u, 2196484647u, 3638700902u,  260302352u, 
    3535293420u, 3116805903u, 1440364029u, 2390388754u,  332129148u, 
    2273583462u, 1740904163u, 3564747422u, 1320315490u, 3688341980u, 
    1943868361u, 3388853410u, 1775902309u, 1365082575u, 1522292425u, 
    1942216237u,  123405003u, 3230794558u,  335674543u,  471852445u, 
    2319546878u,  471339877u, 1623550474u, 1159141530u,  716060172u, 
    2253300242u, 2246457388u, 4177504571u, 2957827037u, 3051182067u, 
    2961392703u, 1339428272u, 1253728860u, 1251798837u, 2071393845u, 
    3652256935u, 3481290805u, 3915495864u, 4240793738u, 2745670169u, 
     223281082u, 1096807079u,  810830859u,  380816886u, 2578459915u, 
    3600280332u, 1900744475u, 2511347346u, 2563321948u, 4072096018u, 
    1553950434u,  262117258u,  938413725u, 2511015293u, 1852340894u, 
    1224529889u, 2111115142u, 3555082594u, 3061142695u,  820280543u, 
     640858393u, 1900651720u,  424329571u, 1689689543u, 2378182011u, 
    3550108203u, 2108998782u, 2907139217u, 1332214261u,  891648241u, 
    2578642005u, 1366249405u, 2619717552u,  574713818u, 1872350222u, 
    2883911152u, 1984517103u, 2452387999u, 3680102565u,  729143999u, 
    3828109877u,  634176716u, 4017428396u, 2044746818u,  570105749u, 
    3900270178u,  579273057u, 2371573676u, 2337057693u,  141475767u, 
    2428598393u,  231339503u, 2618261398u, 3457720245u, 1861956654u, 
    1938640241u, 2038507192u, 1643453033u, 2402192723u, 3391493865u, 
    3602341588u, 1564600188u, 4142473852u, 2286425538u, 3335048275u, 
    3056542298u,  827939153u, 3742963152u, 1076978789u, 1411711112u, 
    3847641540u, 2792235659u, 1291651070u, 4186889356u, 4111150675u, 
     326277337u, 2727536313u, 2521228115u, 3858177828u, 1777628964u, 
    1636457523u, 1327730835u, 3446030271u, 1133158582u, 2674837390u, 
    3258876318u,  782159572u, 4274420083u, 3678751963u,  801318243u, 
    1470311112u, 3354993392u,  776040423u,  840945944u,  688891617u, 
    4262149326u, 3180950192u, 3445687209u,  667765797u, 1822039854u, 
     687782533u, 3130446468u, 1679964477u, 2140412333u, 2521023888u, 
    3474586730u, 2738336824u, 1531194236u,  272855576u,  314578174u, 
    1581144125u, 2538288986u, 1693951845u, 3909226960u, 2978902193u, 
     832218336u, 3075520766u, 1857005512u, 2749313732u, 3217616529u, 
    3198048780u,  168296081u, 3310066596u, 4064434880u,  349245502u, 
    3279951952u, 1874146182u, 2400115994u, 2787873697u,  789599428u, 
    1353028316u, 2138673876u, 2629101256u, 2224129914u, 3943684346u, 
    4270241199u, 4159779981u, 3671560018u, 2926618313u, 4133493471u, 
     886437031u, 2916029412u, 2881600983u, 1733025272u, 2792441416u, 
    4015704600u, 2896243818u, 2059370462u, 1399747019u,  995537401u, 
    2091141688u, 1702053663u, 3365267716u, 3028284675u, 3322651442u, 
    2398992773u, 2459257550u, 3249704119u, 2616019886u, 4275558572u, 
    4064420660u, 4133611408u, 1932472852u, 2298095725u,  837597033u, 
    4139790660u, 4002343555u,  496609365u, 3443323042u,  220968740u, 
     115259491u, 1307168777u,   10893775u, 2491904934u, 2785586805u, 
    2280474953u, 1896693783u, 3870659286u, 2796532337u, 2321646396u, 
    4019162589u, 1855342622u,  555064786u, 2330736969u,  490959045u, 
    3059798279u, 2691359011u,   71617365u,  368895618u, 3439928998u, 
     419018537u,  612072889u, 3479288324u, 2055032196u, 2830468787u, 
    1103099434u, 3041119163u, 1585236715u, 3855831726u, 2842258668u, 
     609983082u,  728464288u, 2536667505u, 1197368241u, 3547774719u, 
     851356113u, 3864312376u,  837825852u, 4273019476u, 1403765610u, 
      93856629u, 3781022335u, 2115174301u, 2023367080u, 4204671851u, 
    1735035239u, 1350209486u,  769793322u, 2369278308u, 4161501167u, 
    2513836932u, 1750009075u, 1668300176u, 3627045746u, 2923342051u, 
    2642801157u, 2226004008u, 1617532275u, 1001520657u, 3767466920u, 
    1885880162u, 3370915495u, 2599368591u, 1996963441u, 2277814872u, 
    3496004282u, 3274173931u, 3858788183u, 3552951969u, 1843565531u, 
     115543966u, 1435933937u,  452057997u, 2562579798u, 3334697064u, 
    3874021024u,   92244728u, 3015352427u, 3170041258u, 1621157335u, 
     953309163u, 3156611667u, 2110349192u, 4097840272u, 1196730082u, 
    2331364547u, 3304400427u, 2319736876u, 3001421795u, 1336205705u, 
    4237191249u,  305950166u, 1712705041u,  781600154u, 3624113458u, 
     399384395u, 2120599518u, 1990671162u, 3380471556u,   40082822u, 
    2409046702u, 3930006359u, 4012814795u, 2760554721u, 3939403736u, 
       6094787u, 3297788831u,  130503754u, 1026191227u,  895372775u, 
    3125416230u, 1954064714u, 1284624943u,  546603443u, 3626978360u, 
      37141541u,   83539007u, 3122783124u,  606885410u, 1520918647u, 
    2239843287u, 3351989811u, 3057238962u, 1875425985u, 1530721995u, 
    1874988534u,  161234343u,  211369000u, 1095654062u,  213167395u, 
     250191778u,  391272265u, 2423828544u, 2551369610u, 3042101804u, 
    1035448140u,  609081370u, 3613652780u, 1185846656u, 3681700798u, 
    2614952462u, 4138682884u, 1223079049u, 2099808600u, 2225489336u, 
     946224690u,  660451857u,  971558712u, 3554881734u, 2305486057u, 
    2318507706u, 3273236262u, 2822055016u, 1492789566u, 1119554775u, 
    1980975322u, 3551807758u, 2745874641u, 3516761755u, 3939928313u, 
     934855953u,  693948913u, 3327192365u, 3073630675u,  101876780u, 
    2481369570u, 1459509195u, 1861004954u, 1141309060u, 3797793840u, 
    1224681030u, 1688144430u, 2547349531u,  768692429u, 1521051682u, 
    2720147032u,  930600186u, 2680061978u, 2879962111u, 1408498461u, 
     268182619u, 3448709763u, 1592216145u, 4292724704u, 1599508620u, 
    4213269118u, 4200181833u,  545619507u, 3236090571u,  997463821u, 
    3184203691u,  101500669u, 4217240112u, 2608903190u, 3784923509u, 
     475922416u, 1479115092u, 1750025272u, 1715568033u, 3797080982u, 
    1579103843u, 2354212356u,  151342425u, 1584856153u, 2496419603u, 
     894839189u, 1937607745u, 1893836937u, 3229688482u, 4106831221u, 
     289431749u,  532687253u, 3202403809u, 2021912759u, 1229083658u, 
    3680341718u, 1058577411u,  186360648u, 2192860281u, 2970507375u, 
    2648231048u, 4204710567u,  352803166u, 1216626353u, 3225302463u, 
     574582876u, 3263983952u, 2943253852u, 1230198514u, 3906077570u, 
     824346422u, 2623662301u, 3956313178u, 3865396696u,  757224614u, 
     830791623u, 3022714332u, 3240228920u, 1179843786u, 1487178451u, 
    2948056279u, 1797982458u, 4255319781u,  668811578u, 3585348844u, 
    3517580725u, 2599889368u, 2684026125u,  349060894u, 3172092854u, 
    3347081959u, 3457931495u, 3830541864u,  288719121u, 1581629673u, 
    4083613336u,  368413676u, 2137076974u, 3970376737u, 3243326972u, 
    2737649035u, 3188605479u, 3616098576u, 3569674338u, 1397648422u, 
     672170313u, 1282546981u, 1964125989u, 2005736712u, 2654721419u, 
    1122965097u, 4003697003u, 4268477949u, 3586676653u, 2818808298u, 
    3845814717u, 4128499149u, 2501897997u, 3860552691u, 2502878480u, 
    1499525956u, 3671878952u,  587611744u,  149747060u,  195690614u, 
    3802850345u, 2325782175u, 1751190503u,  583241465u,  156259644u, 
    2004610888u, 3204681020u, 2689211891u,  664984504u, 3604535295u, 
     618081556u, 3929972522u, 2602574315u, 1710016283u, 1092986901u, 
    3041253464u, 1392231705u, 3940751328u, 1725678863u,  534546529u, 
    1745360123u, 3943952830u, 1658678333u,  821965910u, 2619078892u, 
    1399242525u,  716790203u, 2665205988u,  807849282u, 3088407631u, 
     406427894u, 3934651902u, 1388074483u, 1077200174u, 3305393652u, 
    1386026765u, 1005529155u, 1606082383u, 3179845493u,  956152124u, 
    2975632437u, 1808432395u, 3539388960u, 2114561910u, 3556136492u, 
    2063776030u, 1260005679u, 2450967374u, 1328730778u, 3569386647u, 
    2246395892u,  958560479u, 1397148536u, 2977661875u, 3572736354u, 
    3484318978u, 3480189603u, 3538510658u, 2392289338u,  553042652u, 
    1129421929u,  657031522u, 2923009585u, 1833485762u, 1003532627u, 
    1380103857u, 1960332028u, 1889542857u, 1651702217u, 3630760968u, 
    2313275557u, 1716182045u, 4259335064u, 1188243733u, 3243646919u, 
    1943239771u, 4211021527u, 1276150468u, 1008383770u, 2592475956u, 
    2270143981u, 4206016496u,  220916187u, 1061014409u, 3250755412u, 
     405813977u, 2585483415u, 2282646335u, 3681511559u, 2796349024u, 
    4244618003u, 1140587439u, 3992105438u,  430549136u, 1758853233u, 
    4072612623u,    1466574u, 1215975886u, 2323054716u, 2601488966u, 
     892196231u,  516847440u,  941815809u, 4267193699u, 1399327243u, 
    1513367522u,  412099598u, 3006457623u, 3210632622u, 2929320506u, 
    3214821475u, 2787332623u, 2333453280u, 2286517530u, 1452267238u, 
    1233666122u, 3574845880u,    2697674u, 2373279437u, 1248356043u, 
    4112616366u, 2665803324u, 3834689917u, 2583683474u, 1531171380u, 
    2210054590u, 2346778254u, 2801479353u, 1488986759u, 4262756833u, 
    2674917603u, 2380821100u, 3421476965u, 1420809174u, 3203508306u, 
    2821835379u,  539174012u, 3238947696u, 3532155363u,  463909612u, 
     108020580u,  686311412u, 1779958481u, 3501283419u, 3141371161u, 
    2549322549u, 3355975804u,  151660038u, 1577481000u,  237654147u, 
    3199183092u, 1395812589u, 3832258389u, 3321416658u, 1041973628u, 
    1338155692u,  556614774u, 2802833609u,  966659181u, 3371464856u, 
    1503298306u, 4194717924u, 1233019036u, 2234408174u, 3983530663u, 
     304386537u,  220390885u, 3672604251u, 2545484329u, 1481477612u, 
     699645452u, 1206554024u, 3600925349u, 2351947411u,  719668723u, 
    1522666126u, 2156935220u, 2578961309u, 4292087425u,  851501823u, 
    1526462106u, 1538145242u,  202197234u,  923797659u,  917665233u, 
    1280176282u, 1708706026u, 1488528898u, 1433093941u,  328725394u, 
     986135364u,  789495949u, 4020605538u, 1543114480u, 2934273484u, 
    2050902067u, 4132247293u, 3175607941u, 1881080451u, 3551141606u, 
    4038715194u, 1337862187u,   25058210u, 3386659863u, 2621248714u, 
    4116323910u, 3440594177u,  239971622u, 1000648070u,  346758228u, 
    4004922487u,  486542737u, 3278188663u, 2457877853u, 3549573731u, 
    2257175936u, 2463007358u, 4094271342u, 3404112349u,  913435793u, 
    1413221177u, 3109328087u,  959761872u, 3135335463u, 1341689139u, 
     361014125u, 2510509240u, 1077003967u, 3564454102u, 1902586361u, 
    1247526901u, 2940736338u, 1728957925u, 3861749142u, 3702507913u, 
       6506179u, 2640286243u, 3185951192u, 4257119115u, 4170283151u, 
     874880000u,  960224933u, 3552835960u, 4133901877u, 2902803543u, 
    4029723476u, 1069229844u, 1097566470u, 2043483688u, 3492749477u, 
    1714015065u,  997956638u, 2574567667u, 3733818679u, 3438219097u, 
    3601196803u,  451266934u, 3291888764u, 3528067348u, 4204683957u, 
    3612438284u, 1162023843u, 1522592715u, 2943081924u, 1847134284u, 
     663478404u, 2457748727u, 3297874754u, 3010019326u,  387951882u, 
    3188883299u, 3829156090u, 3255087638u, 3365242650u, 1671295327u, 
    2343810092u, 1843840147u,  693346359u, 4107469050u,  492532155u, 
    2460893290u,  532996711u, 3649528417u, 2356748197u, 1186894091u, 
    2134551200u, 2672859557u, 3034429947u, 2526994202u, 2366878138u, 
    4138065547u, 2062701434u,  368949266u, 2351844505u, 2149626396u, 
     419191055u, 2240210598u, 1407993071u,  387260016u, 4097232872u, 
    3885512949u, 2155071777u, 3798421539u, 4274030102u, 1885446249u, 
    2981237059u, 3357473073u,  137290838u,  637652444u,  287471442u, 
    2662089150u, 2298526392u, 1119370200u,  478113897u, 1914078872u, 
     723733797u, 3624950286u, 3707741573u,  842693726u, 1780406925u, 
    1305032792u, 1968510495u, 2075734367u, 3590755543u, 1450891707u, 
      83344440u, 3429470524u, 3773462330u, 4241226826u, 3307743815u, 
     683104062u, 1884612196u, 1017390927u, 1347475469u, 3016083386u, 
    1524948889u, 1612638509u, 2128788363u, 4182030709u, 3347916223u, 
    4176020545u, 2603962123u, 2764662049u, 3055322347u, 3694096552u, 
     458347065u, 1726076036u, 2583701940u, 2714122091u, 4113553423u, 
    4231559144u, 1222406883u, 2402937181u, 1283962072u, 4009746733u, 
    3536942113u, 3093850505u, 2103058130u, 2078929575u, 4256494377u, 
    2744617663u, 1636520641u, 3812371327u, 1841438767u,  853567863u, 
     293694107u, 1698085228u,   77712651u, 4261360454u, 3773698328u, 
    1728087008u, 3789317723u, 2829767026u, 4156170415u, 3871260724u, 
     905192820u, 4275132168u, 2305686413u, 2805314924u, 2583657764u, 
     465730905u, 4205645334u,  155108597u,  696964616u, 2654681637u, 
    3442801575u, 2435866492u, 3014889847u, 4131606733u, 3379831463u, 
    3204498570u, 4096439241u, 2845484976u, 2127645355u, 2247613591u, 
    2703254578u, 1116237411u, 4213484460u, 4131731766u, 3202543611u, 
    2320158681u, 2454537032u,  130009356u, 2406857045u, 2990647864u, 
    1084825589u, 2232163876u, 3955791431u,  253534309u,  274296365u, 
    3822676536u,  264436337u, 1418207815u, 3310289547u,  986559116u, 
    3853187406u,  489405686u, 3596088854u, 1335402887u,  787430740u, 
     981109357u, 1197534756u, 2800306525u, 1916853569u,  284155565u, 
    2610413878u, 1182968776u,  106675122u, 1210408692u, 4251329608u, 
    3779855792u, 3736145590u, 1908384358u,  970818599u, 3246626431u, 
    3742565154u, 2591138191u, 3747660557u, 3364101596u, 2311379507u, 
     489328382u, 2031550691u, 4202899902u, 1584951024u, 3644694974u, 
    3312357739u,  217525025u, 3644269603u, 2002321607u, 3954860816u, 
    1398670148u, 2917504255u, 2706710400u,  220857550u,  989127374u, 
    2244289149u, 2490586984u, 2642071963u, 2590536648u, 4115793618u, 
    2576461102u, 1363138228u, 1925983082u, 1189640964u,  152142597u, 
    1764120035u, 2206817911u, 3313705895u, 1751187711u, 4081059871u, 
     464054176u, 2379176226u, 1975150787u,  340197618u, 1936526659u, 
    3404850845u, 2367129719u, 2924126064u, 3459185214u, 2363113359u, 
    3010128150u, 1881108460u, 3746222960u, 2651248795u,  224163596u, 
     508682106u,  943524043u, 2151289167u, 1974147403u, 1247690780u, 
    4116870452u, 2079216305u, 3393218954u, 3567954541u, 1940786677u, 
    1574417861u, 1432063148u, 2739922267u,  253812427u, 2591454480u, 
    3182164041u, 1793274063u, 2176665906u, 2497827999u,  858673115u, 
    3096781115u, 1834782321u, 3629534222u,  724519201u, 4056372476u, 
    3228503710u,  577268130u, 1582054841u,  301959526u, 4045076624u, 
    2865028790u,   73755492u, 1825462177u, 3560768027u, 1981121873u, 
    2691187765u,  188128347u, 2313898662u,  997804738u, 2793909018u, 
    3725300670u, 3120850068u, 3968046994u,  405825309u, 1595162944u, 
    3769151350u, 2640525979u,   61684932u, 1415789469u, 1264020135u, 
    3950226460u,  772728513u,  971672615u, 3978403595u,  588202301u, 
     292832750u, 1395744634u, 2495776388u, 3271786154u, 2736543666u, 
    2060545333u, 2797180204u,  141652380u, 3713523292u,  433967869u, 
     240314286u, 1601436731u, 3508366246u, 2271914741u, 2271704699u, 
    3087042934u, 2982212958u, 2930329007u,  912272095u, 2555606130u, 
    2333369619u,  230283885u, 3017301575u, 3446194064u, 4107855164u, 
    1100310667u, 1909294076u,  434149393u,  366780871u, 3555380811u, 
     246274064u, 1400899690u, 2703469266u,  570232921u, 3419563051u, 
    1660365526u, 2968644183u, 1329342932u, 1483085977u, 3122684163u, 
    4066546606u, 3861009980u, 2234200415u, 2739937896u, 4096595764u, 
     768251542u,  316090862u,  124090419u,  889195424u, 2979770918u, 
    3328719122u, 1415047028u, 3926406796u, 1428546568u, 3361029438u, 
    4211665632u, 1269309700u, 1527101308u,  652172402u, 3674640971u, 
    3641747964u, 3660382256u, 3370924808u,  115498466u, 1163212438u, 
    3820703862u,  978439546u,  921271064u, 1378784223u, 3577406236u, 
    3562940814u, 2671627138u, 3531245640u,  693194205u, 2451064185u, 
    2578017243u, 2455989585u, 2481212951u, 1228439114u, 3012282683u, 
    3002755761u, 3856715509u, 3419901832u,  211338799u, 1896610556u, 
    3548852272u, 1916481449u, 2574085613u, 2000004829u, 2000481307u, 
    1198464170u, 3173831883u, 2900714882u, 3372201736u, 3881209586u, 
    2588621608u, 3902089006u, 4177227927u, 3209186455u,  900943443u, 
    1118888408u, 2571008108u, 2961971973u,  161380270u,  566208408u, 
    1721643267u,  530432053u,  515707945u,  819921504u,  992966575u, 
     625914594u, 1250102554u, 2512743175u, 3531636148u,  315086074u, 
    1566977546u, 3531864233u,  930010731u, 3104844610u, 2733910504u, 
    3976529992u, 1345375192u, 2115866656u, 1763704995u, 2812700617u, 
    3160963817u, 3823051215u, 3657060267u, 2312949751u,  322667309u, 
    1212061965u,   72459214u, 4191705628u, 2896389243u,  156446385u, 
    4016046429u, 1401209769u, 1582631648u, 4179061694u, 3916756276u, 
    1567803172u, 2638882606u, 1327787509u, 1976869919u,  519314732u, 
    2342793709u, 3933183772u,  758814231u,  581874432u, 4123546062u, 
    1426435462u, 3733828360u, 3854646810u,  359046114u, 2145975155u, 
    3266914361u, 2642642879u, 4016733328u, 2504537053u,  424148936u, 
    2998977786u, 2572729225u,  125981442u, 1724033108u, 2267238861u, 
    4289876504u,  137751831u, 2478124794u, 3552549223u, 1304521882u, 
    1460229647u,  796181928u, 3636595890u,  745804678u, 1056860767u, 
     974631484u, 2497485889u, 3198571182u, 4027291544u, 1320904721u, 
     205244833u, 3484057229u,  231832262u, 3335419183u,   88553761u, 
    2986770319u, 2926927914u, 3677485767u, 2571089926u, 3267182695u, 
     489755279u,  671960175u, 3419847717u, 3886885702u, 2653648091u, 
     211741983u,  301564791u, 2853589419u,  297550915u, 1272390376u, 
     584147277u, 2971264785u, 3388262418u, 2419292619u,  396848377u, 
     400462790u, 1021638674u, 3544744847u, 1046459817u, 1131154364u, 
     450207978u,  974999278u, 3686597032u, 1290348400u, 2998745183u, 
    1317492534u, 3151398478u,  276900107u, 2794007767u, 1755609205u, 
    2217365206u, 1595486548u, 1401826344u, 4027763770u, 2842307113u, 
    2474293622u,  504939907u, 1018556149u,  634870958u, 2105780331u, 
      84888587u, 1118262728u, 4141601466u,  730125637u, 4167719882u, 
     949159370u,  531976824u, 3685828907u, 2007510762u, 3599556892u, 
    2820479277u,  492851583u, 1246337526u, 1940706935u, 3240710205u, 
    2042152385u, 2397098757u, 3475438049u, 1837355219u,  986711571u, 
    1147589739u, 1298991474u, 3237271788u, 1639728592u, 3858496958u, 
     993191411u, 3128643299u,  914694463u, 1747322140u, 1525827943u, 
    4030035866u,  967493702u, 1097052573u, 2880094426u, 2289918684u, 
    3468759489u, 4100640951u, 2142548389u, 1149966939u,   79830251u, 
    1074105259u, 2505154460u, 3984323976u, 3599632907u,  294558951u, 
      17254381u, 1285914862u, 2776786651u, 2540831914u, 3765303330u, 
     873163177u, 1692514385u, 2731097567u,  979124410u, 3428974151u, 
     467084174u, 2154789608u, 1647267729u, 2795216860u, 1039042602u, 
    3418600624u, 3228166887u, 1002332673u, 3974411194u, 2580583607u, 
     904733688u,  483022231u, 3917358149u, 2215196638u,  654516857u, 
    3598498336u, 4099774739u, 3954763417u, 1118670512u, 2139872644u, 
    3082249575u, 1192330715u,  420290154u, 2802551881u, 2603975185u, 
    3939768357u, 1474219045u, 2189743776u,  410209795u, 4184120550u, 
    2546630001u,  847306611u, 1677378142u,  477535865u, 3916441108u, 
    1277126944u, 2864665523u, 1702604657u,  773876494u, 1807131889u, 
    3702786021u, 1337776463u, 3572687626u, 2980033697u, 4255621298u, 
     394586502u, 3130582261u, 1726957441u, 3873244108u, 1267791874u, 
    3719934631u, 1316393651u, 1375414654u,  453381607u,  568651816u, 
    2550470125u, 3901112416u, 1214305419u, 3751458762u,  666671791u, 
    1284096272u,    2828953u, 3723372638u, 1218033032u, 2368557457u, 
    2365714712u,  848058200u, 3740496416u, 1949250944u,  181477083u, 
    3214116591u, 3885751315u, 3539347299u,  562529426u, 1283372361u, 
    3580838576u,  794172702u, 3437985472u, 2640564784u, 3942264960u, 
    2252660330u,  589714749u,  355166505u, 2167808774u, 3911578180u, 
    1739283430u,  582727528u,  745486761u,  709694981u, 2470394812u, 
    2784288873u, 2603686201u, 2503004545u,  921037450u,  248723197u, 
    2233092030u, 4241673838u, 4248520683u, 4035718652u, 2104169607u, 
      51010521u, 2984457723u, 2807166639u, 1767043292u, 3958216011u, 
     149364986u,  186549740u, 1257701956u,  553198631u, 3442166049u, 
     725301812u, 1488214709u, 3955036524u,  357839254u, 3523734991u, 
    2195185139u, 3754986293u, 1575537478u, 2389854207u, 3176040305u, 
     208578128u, 2253741825u, 2553968314u, 3455390865u, 1293117228u, 
    3508606804u, 1846102791u,  813773800u, 3404247876u,  531259344u, 
    3216075103u, 3526153030u,  456016676u, 2739749423u, 1093250703u, 
      69234044u,  792168263u, 3848095809u, 2202850158u, 2213519030u, 
    1007229102u, 2338703931u, 1765185701u, 2604649447u, 1522222943u, 
    3266048702u, 1921662655u, 3673686829u, 3415463996u, 1644407479u, 
    1107992188u,  363565489u, 3321072547u, 3151961821u, 3445798495u, 
    1425883319u, 4059119275u, 3606696770u, 2834384682u, 1596539449u, 
    3636233163u, 3557157499u, 3602705437u,  758141738u, 1412595934u, 
     556283557u, 2057068993u, 3779071200u, 1445808087u,  189318428u, 
    2040772438u, 2949440024u, 2802944456u, 3151530650u,  722184665u, 
    1877641340u, 1164797906u, 1631395717u, 1861106618u, 4207596651u, 
    3412368205u, 1713663690u, 2877098665u, 1890588414u, 2270170721u, 
     673484753u, 1712353108u, 1400306575u, 3682940464u, 1348885721u, 
    2224151036u, 3841851095u, 3451954494u, 1060960786u,  437589053u, 
    1334356198u, 2804921297u, 1756078580u, 3810757529u, 3040883626u, 
    2579239042u,  616918759u, 2853014080u, 3742299785u,  565628891u, 
     357151864u, 2285145814u, 1983148904u, 2565821297u,  130519865u, 
    3057750354u, 3234971651u,  981709724u, 3006660375u, 2608421078u, 
     921323098u, 1324171014u, 2920168401u,  633540935u, 2393553830u, 
    1860716086u, 3653638057u, 2418826530u, 2399020543u, 1069386495u, 
    3873088393u, 1540601308u, 1801814819u,  379787626u, 1538149557u, 
    3623779521u, 2100185394u, 2590016350u, 1099349030u,   83020443u, 
    3990751639u,  908730558u, 2004705277u,  566260495u, 1090955400u, 
    2559442672u, 1852069143u, 1139673340u, 3017343395u, 4132204778u, 
    1727993619u, 3383152526u,  780997206u,  935658414u, 3677570543u, 
    1746642030u, 2509125172u,  223854197u, 1604508661u, 1891081055u, 
     952170820u, 1620251131u,  940572554u, 3971328146u, 2242971249u, 
    4255333609u, 1861536355u, 3727697922u, 3183876408u,  286776617u, 
     302578855u, 2532118292u, 3639269404u, 2970666689u, 2920063380u, 
    1694233198u,  586913821u, 3422958506u, 3686809331u, 1981091823u, 
     858281024u,  814684694u, 2608505099u, 1816299992u, 2332360436u, 
    3899354093u,  697179254u, 1558653496u,   24279715u, 4124089548u, 
    3313503461u, 2741421184u, 3284737548u,  873011879u, 1808479090u, 
    3455057368u,  244010779u,  303799249u, 2515764191u, 3793164333u, 
     747991075u,  975903908u, 3129358949u, 1966190241u, 2294762589u, 
    3495328008u, 1086902846u, 3177987384u, 3938728764u,  867407692u, 
    3256420714u,  689048646u, 3809767992u, 2344280344u,  295485905u, 
     928125706u,  788247606u, 1836899313u, 3165702953u,  298675190u, 
    2992367488u, 2519000176u, 3337159108u, 2044324637u, 2155658777u, 
    2552272156u, 1827494965u, 2257947328u, 2625243482u, 4130751842u, 
    };

int main(
    int			argc,
    char *		argv[])
    {
    unsigned long	i;
    uint32_t		(*funcptr)(void);
    uint32_t		random_value;
    uint64_t		longlong_value;
    double		double_value;
    volatile uint32_t	dummy_long;	/* Avoids optimization; see below */
    volatile uint64_t	dummy_longlong;
    volatile double	dummy_double;
    uint32_t		goodseedresult;
    FILE*		savefile;
    uint32_t		seedresult;
    static mt_state	state;
    struct rusage	then;
    struct timeval	timeofday;
    static unsigned long
			timing_loops = TIMING_LOOPS;

    setbuf(stdout, (char *) NULL);

    /*
     * If the user has given a number of timing loops, reset the loop count.
     */
    if (argc > 1)
	timing_loops = atol(argv[1]) * TIMING_LOOP_BASE;

    /*
     * Compare the generated values against corresponding numbers from
     * Matsumoto and Nishimura's own generator, to make sure we're
     * doing the calculation correctly.
     */
    (void) printf ("Validity test...");
    mt_seed32new(5489);
    savefile = fopen("mtsave", "w");
    mt_savestate(savefile);
    fclose(savefile);
    mt_seed32new(1);
    savefile = fopen("mtsave", "r");
    mt_loadstate(savefile);
    fclose(savefile);
    unlink("mtsave");
    for (i = 0;  i < sizeof correct_values / sizeof correct_values[0];  i++)
	{
	random_value = mt_lrand();
	if (random_value != correct_values[i])
	    {
	    (void) fprintf (stderr,
	      "Failure at value %ld: expected %" PRIu32 ", got %" PRIu32 "\n",
		i, correct_values[i], random_value);
	    return 1;
	    }
	}
    (void) printf ("passed.\n");

    /*
     * Make sure we can take a pointer to the inlined functions.
     */
    funcptr = &mt_lrand;
    random_value = (*funcptr)();

    /*
     * Timing tests.  Each test sums up the random numbers, not
     * because we care about the sum, but because the PRNG functions
     * are inlined.  If we don't sum up the numbers (and then assign
     * them to a volatile), the compiler will optimize the RNG code
     * right out of existence.
     */
    (void) printf ("%ld default longs took            ", timing_loops);
    getrusage(RUSAGE_SELF, &then);
    for (i = 0;  i < timing_loops;  i++)
	random_value += mt_lrand();
    report_timing(timing_loops, &then);

    (void) printf ("%ld state-based longs took        ", timing_loops);
    getrusage(RUSAGE_SELF, &then);
    for (i = 0;  i < timing_loops;  i++)
	random_value += mts_lrand(&state);
    report_timing(timing_loops, &then);

    dummy_long = random_value;
    (void)dummy_long;			/* Silence compiler warning */

    longlong_value = 0;

    /*
     * In the case of long longs, there aren't enough registers to
     * store them on a 32-bit x86, so they wind up on the stack.  We'd
     * get faster timing if we just stored directly into
     * dummy_longlong.  However, this would produce worse results on
     * more sensibly designed machines.  Rather than tune our code to
     * a broken architecture, we'll stick with the generalized
     * version.
     */
    (void) printf ("%ld default long longs took       ", timing_loops);
    getrusage(RUSAGE_SELF, &then);
    for (i = 0;  i < timing_loops;  i++)
	longlong_value += mt_llrand();
    report_timing(timing_loops, &then);

    (void) printf ("%ld state-based long longs took   ", timing_loops);
    getrusage(RUSAGE_SELF, &then);
    for (i = 0;  i < timing_loops;  i++)
	longlong_value += mts_llrand(&state);
    report_timing(timing_loops, &then);

    dummy_longlong = longlong_value;
    (void)dummy_longlong;		/* Silence compiler warning */

    double_value = 0.0;

    /*
     * Similarly, the x86 winds up storing the double-precision sum on
     * the stack.  Again, we'll tolerate that inefficiency.
     */
    (void) printf ("%ld default fast doubles took     ", timing_loops);
    getrusage(RUSAGE_SELF, &then);
    for (i = 0;  i < timing_loops;  i++)
	double_value += mt_drand();
    report_timing(timing_loops, &then);

    (void) printf ("%ld state-based fast doubles took ", timing_loops);
    getrusage(RUSAGE_SELF, &then);
    for (i = 0;  i < timing_loops;  i++)
	double_value += mts_drand(&state);
    report_timing(timing_loops, &then);

    (void) printf ("%ld default long doubles took     ", timing_loops);
    getrusage(RUSAGE_SELF, &then);
    for (i = 0;  i < timing_loops;  i++)
	double_value += mt_ldrand();
    report_timing(timing_loops, &then);

    (void) printf ("%ld state-based long doubles took ", timing_loops);
    getrusage(RUSAGE_SELF, &then);
    for (i = 0;  i < timing_loops;  i++)
	double_value += mts_ldrand(&state);
    report_timing(timing_loops, &then);

    dummy_double = double_value;
    (void)dummy_double;			/* Silence compiler warning */

    /*
     * Test seed timing.
     */
    (void) printf ("Initializing from mt_seed took          ");
    gettimeofday(&timeofday, NULL);
    seedresult = mt_seed();
    report_clock_timing(&timeofday);
    if (seedresult == 0)
	(void) printf ("OOPS! Got zero seed from mt_seed!\n");

    (void) printf ("Initializing from mt_goodseed took      ");
    gettimeofday(&timeofday, NULL);
    goodseedresult = mt_goodseed();
    report_clock_timing(&timeofday);
    if (goodseedresult == 0)
	(void) printf ("OOPS! Got zero seed from mt_goodseed!\n");
    if (seedresult == goodseedresult)
	(void) printf ("OOPS! mt_seed and mt_goodseed both returned 0x%x!\n",
	  seedresult);

    (void) printf ("Initializing from mt_bestseed took      ");
    gettimeofday(&timeofday, NULL);
    mt_bestseed();
    report_clock_timing(&timeofday);

    return 0;
    }

static void report_timing(
    unsigned long	loops,		/* Number of loops that were done */
    struct rusage *	then)		/* Time test started */
    {
    long		diff;		/* Difference in times */
    long		microdiff;	/* Microsecond part of difference */
    struct rusage	now;		/* Time test ended */
    double		secs;		/* Actual seconds needed */

    getrusage(RUSAGE_SELF, &now);
    diff = now.ru_utime.tv_sec - then->ru_utime.tv_sec;
    microdiff = now.ru_utime.tv_usec - then->ru_utime.tv_usec;
    if (microdiff < 0)
	{
	diff--;
	microdiff += 1000000;
	}
    secs = diff + (microdiff / 1000000.0);
    (void) printf ("%3ld.%6.6ld seconds (%ld/sec).\n", diff, microdiff,
      (long)(loops / secs));
    }

static void report_clock_timing(
    struct timeval *	then)		/* Time test started */
    {
    long		diff;		/* Difference in times */
    long		microdiff;	/* Microsecond part of difference */
    struct timeval	now;		/* Time test ended */
    double		secs;		/* Actual seconds needed */

    gettimeofday(&now, NULL);
    diff = now.tv_sec - then->tv_sec;
    microdiff = now.tv_usec - then->tv_usec;
    if (microdiff < 0)
	{
	diff--;
	microdiff += 1000000;
	}
    secs = diff + (microdiff / 1000000.0);
    (void) printf ("%3ld.%6.6ld seconds.\n", diff, microdiff);
    }
